Batch 3 - Class 202 - Finite State Machines

• (MartinShColl 9.20) There is a cake with square top and four sides frosted. We want to cut the cake into 7 pieces, so that each piece has the same volume and same area of frosting.
• Answer: Divide the square perimeter into seven equal segments and cut vertically. The perimeter acts as base of triangles to calculate the top surface area of frosting, and hence equal (the side frosting is equal because base and height are same). The volume is the top surface area multiplied by height, and hence again equal.

• Start with the Fickle Fruit exercise. Each group should select a member to be the fruit vendor (take turns). The vendor gets the Fickle Fruit instruction card. The other members of the group are the fruit buyers, and they are not allowed to see the instruction card.
• Following the instructions on the card, the vendor dispenses fruit depending on the requests of the other students in the group. Let them practice making and filling fruit requests for a few minutes. It may be more appropriate for the teacher to be the fruit vendor for the younger students. Encourage them to keep some kind of record of the vendor's behavior.
• Challenge them to come up with a sequence of requests which gets them 3 apples in a row. If they get this very quickly, ask them how to get something else. Ask them if they completely understand the behavior of the vendor, and can predict his/her behavior.

• Repeat the previous steps, this time using the Frustrating Fruit instruction card.
• Eventually, someone will say that they can't get 3 apples in a row. Ask if they're sure! (They can't get 3 in a row. We'll be able to see why later.)

• Explain notion of states, inputs and outputs - explain that there is no uncertainty in behavior of the vendor. It is all deterministic. An input in any state leads to an output and a state transition.
• Simple Chicken Life Cycle Example

  
  

  
• Work with kids to draw state diagram for Fickle Fruit example - recreate all possible state/inputs and let the kids articulate the output and transitions.
• Every state must have an output and transition for every input.
• Work with kids to draw state diagram for Frustrating Fruit example. Make sure they understand the representation.
• Why can't we get three apples in a row?

• Pass the Fancy Fruit instruction card. Let kids play and come up with their own individual state diagrams. They may need help with finding states - they can also add them as they observe it.
• Discuss the state diagram for Fancy Fruit exercise. Explain that states that have identical transitions can be collapsed.

• Discuss the programming of FSM through rules (if-then-else) statements. Need to store the state in a given variable.
• Discuss alternate programming style by storing the entire state machine in a table, and looking it up, depending on current state and input.
• This program could potentially solve any problem which can be modeled as a FSM, just by changing the table

• A farmer wants to take a wolf, a goat, and a cabbage to market. To do this, he must cross from the east to the west side of a river using a boat that can only carry him plus one of his three possessions. He can not leave the wolf and the goal together unsupervised, nor the goat and the cabbage.
• Solve the problem above
• Think of it as a state diagram (Kids may need a hint that any state is fully described by items on the east bank). The figure below does not have actions marked - encourage kids to do that.

• Complete the state diagram for the wolf-goat-cabbage problem
• Think of tic-tac-toe as a state machine. Draw the states and transitions
• Program one of the finite stage machines above (or one of your choice) using App Inventor